<?php

// Given a matrix (2D array) of m x n elements (m rows, n columns), 
// write a function that prints the elements in the array in a spiral manner.
//
// Solution: 
// Assume clockwise.
// 1) Start at (0,0) Print first row, last column, last row, first column (without the starting point)
// 2) The starting point is (1,1), we repeat the same process for the remaining matrix (Sub-problem identified)
//
// Clearly, a Dynamic Programming solution will be great 

require_once 'util.php';

$m = 4;
$n = 4;
$arr = generateRandomArray(10, 99, $m * $n);

// Matrix init
$matrix = array_chunk( $arr, $n );

// Print normal
for( $i=0; $i<$m; $i++ ){
	for( $j=0; $j<$n; $j++ ){
		printf( "%-8d", $matrix[$i][$j] );
	}
	echo "<br/>";
}

printMatrixSpiral( $matrix, 0, 0, $m, $n );

// Print the matrix in a spiral manner, starting with row $i, column $j, having $m rows and $n columns
function printMatrixSpiral( $matrix, $i, $j, $m, $n ){
	if( !$matrix ) return;

	// Ending condition
	if( $m < 0 || $n < 0 ) return;

	// Print first row
	$row = $i;
	for( $col=$j; $col<$j+$n; $col++ ){
		echo $matrix[$row][$col]." ";
	}

	// Print last column
	$col = $j + $n - 1;
	for( $row=$i+1; $row<$i+$m; $row++ ){
		echo $matrix[$row][$col]." ";
	}

	// Print last row
	if( $m > 1 ){
		$row = $i + $m - 1;
		for( $col=$j+$n-2; $col>=$j; $col-- ){
			echo $matrix[$row][$col]." ";	
		}	
	}
	
	// Print first column
	if( $n > 1 ){
		$col = $i;
		for( $row=$i+$m-2; $row>$i; $row-- ){
			echo $matrix[$row][$col]." ";	
		}	
	}

	// Next round:
	printMatrixSpiral( $matrix, $i+1, $j+1, $m-2, $n-2 );
}